package problems.contest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class WCT312 {
    // 题一 : 2418. 按身高排序
    public String[] sortPeople(String[] names, int[] heights) {
        int n = heights.length;
        int[][] ass = new int[n][2];

        for (int i = 0; i < n; ++i) {
            ass[i][0] = heights[i];
            ass[i][1] = i;
        }
        Arrays.sort(ass, (o1, o2) -> o2[0] - o1[0]);

        String[] ret = new String[n];
        for (int i = 0; i < n; ++i) {
            ret[i] = names[ass[i][1]];
        }

        return ret;
    }


    // 题二 : 2419. 按位与最大的最长子数组
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int ret = 1;
        int maxNum = 0;

        for (int i = 0; i < n; ++i) {
            maxNum = Math.max(nums[i], maxNum);
        }

        int pre = 0;

        while (pre < n) {
            if (maxNum == nums[pre]) {
                int j = pre;
                while (pre < n && maxNum == nums[pre]) ++pre;
                ret = Math.max(ret, pre - j);
            } else {
                ++pre;
            }
        }

        return ret;
    }


    // 题三 : 2420. 找到所有好下标
    public List<Integer> goodIndices(int[] nums, int k) {
        List<Integer> ret = new ArrayList<>();
        int n = nums.length;
        // dp[i] 表示nums[i, n-1]中以 nums[i] 开始的最长非递减连续序列的长度
        int[] dp = new int[n];

        dp[n - 1] = 1;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] <= nums[i + 1]) dp[i] = dp[i + 1] + 1;
            else dp[i] = 1;
        }

        int pre = 1;
        for (int i = 1; i < n - k; ++i) {
            if (i - k >= 0) {
                if (pre >= k && dp[i + 1] >= k) ret.add(i);
            }
            pre = nums[i] <= nums[i - 1] ? pre + 1 : 1;
        }

        return ret;
    }


    // 题四：并查集
    // 2421. 好路径的数目
    int[] fa;
    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        int n = vals.length;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
        }

        fa = new int[n];
        for (int i = 0; i < n; ++i) fa[i] = i;
        // size[x] 表示节点值等于 vals[x] 的节点个数，
        // 如果按照节点值从小到大合并，
        // size[x] 也是连通块内的等于最大节点值的节点个数
        int[] size = new int[n];
        Arrays.fill(size, 1);
        Integer[] id = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(id, (i, j) -> vals[i] - vals[j]);

        int ans = n;
        for (int x : id) {
            int vx = vals[x], fx = find(x);
            for (int y : g[x]) {
                y = find(y);
                // 只考虑最大节点值比 vx 小的连通块
                if (y == fx || vals[y] > vx) continue;
                // 可以构成好路径
                if (vals[y] == vx) {
                    // 乘法原理
                    ans += size[fx] * size[y];
                    // 统计连通块内节点值等于 vx 的节点个数
                    size[fx] += size[y];
                }
                // 把小的节点值合并到大的节点值上
                fa[y] = fx;
            }
        }
        return ans;
    }

    int find(int x) {
        if (fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }
}
